package lc.递归;

/**
 * @description:
 * @author: qian
 * @createDate: 2021/10/14
 */
public class Math62_不同路径 {

    int[][] res = null;
    public int uniquePaths(int m, int n) {

        res = new int[m][n];
        return dfs(m - 1, n - 1);
    }

    private int dfs(int i, int j) {

        if (i == 0 || j == 0) return 1;

        if (res[i][j] != 0) {
            return res[i][j];
        }
        res[i][j] = dfs(i - 1,j) + dfs(i,j - 1);
        return res[i][j];
    }
}
